package SwordOffer2;

import java.util.Stack;

public class day9_2 {
    /*
     * 1.创建一个栈stack，若head有child，且head的next不为空，stack保存head节点，head.next=child，child的前驱指向head，
     * 2.判断若head没有child，也没有next，head.next=栈顶元素，栈顶元素出栈且前驱指向head。
     * 3.若head的next，child，stack都为空，退出循环。
     * */
    public Node flatten(Node head) {
        Node res = head;
        Stack<Node> stack = new Stack<>();
        // System.out.println(head.child);
        if (head == null) {
            return head;
        }
        while (head.child != null || head.next != null || !stack.isEmpty()) {
            //System.out.println("jin");
            if (head.child == null) {
                //  System.out.println(head.val);
                if (head.next != null) {
                    head.next.prev = head;
                    head = head.next;
                }
            } else {
                //System.out.println("jin");
                if (head.next != null) {
                    stack.add(head.next);
                }
                head.child.prev = head;
                head.next = head.child;
                head.child = null;
                head = head.next;
                //  System.out.println(head.val);
            }
            if (head.next == null) {
                if (head.child == null) {
                    if (stack.isEmpty()) {
                        break;
                    }
                    Node temp = head;
                    head.next = stack.pop();
                    head = head.next;
                    head.prev = temp;
                }
            }
        }
        return res;
    }
}
